package SubjectTree.Three;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.stream.Collectors;

import Utility.TreeNode;

public class PathSum {

/**
 * 难度：中等
 * 
 * 113. 路径总和 II
 * 	给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
 * 	
 * 说明: 叶子节点是指没有子节点的节点。
 * 	
 * 示例:
 * 	给定如下二叉树，以及目标和 sum = 22，
 * 	              5
 * 	             / \
 * 	            4   8
 * 	           /   / \
 * 	          11  13  4
 * 	         /  \    / \
 * 	        7    2  5   1
 * 	返回:
 * 	[
 * 	   [5,4,11,2],
 * 	   [5,8,4,5]
 * 	]
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		PathSum ps= new PathSum();
		System.out.println(ps.pathSum2(TreeNode.MkTree("[1,-2,-3,1,3,-2,null,-1]"), 2));
	}
	//自己写(逐层遍历)
	public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
		List<List<Integer>> list = new ArrayList<>();
		if(root==null)return list;
		Deque<TreeNode> deque = new LinkedList<>();
		Queue<int[]> queue = new LinkedList<>();
		
		deque.offer(root);
		queue.offer(new int[] {root.val});
		
		while(!deque.isEmpty()) {
			int currentLevelSize = deque.size();
			for(int i=0;i<currentLevelSize;i++) {
				TreeNode node = deque.poll();
				int[] temp = queue.poll();
				//遇到叶子
				if(node.left==null && node.right==null) {
					int count = 0;
					for(int t:temp) {
						count+=t;
					}
					//判断数组中的数相加是否等于targetSum
					if(count == targetSum)
						list.add(Arrays.stream(temp).boxed().collect(Collectors.toList()));
				}
				if(node.left!=null) {
					deque.offer(node.left);
					//创建一个新的数组
					int[] t = new int[temp.length+1];
					//把旧数组复制到新数组
					System.arraycopy(temp, 0, t, 0, temp.length);
					//新数组最后一位是放left.val
					t[t.length-1] = node.left.val;
					queue.offer(t);
				}
				if(node.right!=null) {
					deque.offer(node.right);
					//创建一个新的数组
					int[] t = new int[temp.length+1];
					//把旧数组复制到新数组
					System.arraycopy(temp, 0, t, 0, temp.length);
					//新数组最后一位是放right.val
					t[t.length-1] = node.right.val;
					queue.offer(t);
				}
			}
		}
		return list;
    }
	//自己写(递归)
	List<List<Integer>> result = new ArrayList<>();
	Deque<Integer> path = new LinkedList<Integer>();
	public List<List<Integer>> pathSum_1(TreeNode root, int targetSum) {
		if(root==null)return result;
		//把根节点先放进list
		path.push(root.val);
		traversal(root, targetSum);
		return result;
    }
	public void traversal(TreeNode root, int targetSum) {
		//遇到叶节点
		if(root.left==null && root.right==null) {
			//如果等于目标数,则保存该数组
			if(root.val == targetSum) {
				List<Integer> temp = new LinkedList<Integer>(path);
				//因为path是按照先入后出顺序,所以要把数据倒过来
				Collections.reverse(temp);
				result.add(temp);
			}
		}
		if(root.left!=null) {
			path.push(root.left.val);// 添加数据
			traversal(root.left, targetSum - root.val);
			path.pop();// 回溯
		}
		if(root.right!=null) {
			path.push(root.right.val);// 添加数据
			traversal(root.right, targetSum - root.val);
			path.pop();// 回溯
		} 
	}
	//方法一：深度优先搜索
	List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Deque<Integer> path1 = new LinkedList<Integer>();
    public List<List<Integer>> pathSum1(TreeNode root, int sum) {
        dfs(root, sum);
        return ret;
    }
    public void dfs(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        path1.offerLast(root.val);
        sum -= root.val;
        if (root.left == null && root.right == null && sum == 0) {
            ret.add(new LinkedList<Integer>(path1));
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
        path1.pollLast();
    }
    //方法二：广度优先搜索
    List<List<Integer>> ret2 = new LinkedList<List<Integer>>();
    Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();
    public List<List<Integer>> pathSum2(TreeNode root, int sum) {
        if (root == null) {
            return ret2;
        }

        Queue<TreeNode> queueNode = new LinkedList<TreeNode>();
        Queue<Integer> queueSum = new LinkedList<Integer>();
        queueNode.offer(root);
        queueSum.offer(0);

        while (!queueNode.isEmpty()) {
            TreeNode node = queueNode.poll();
            int rec = queueSum.poll() + node.val;

            if (node.left == null && node.right == null) {
                if (rec == sum) {
                    getPath(node);
                }
            } else {
                if (node.left != null) {
                	//通过哈希表,把子节点与父节点关联
                    map.put(node.left, node);
                    queueNode.offer(node.left);
                    queueSum.offer(rec);
                }
                if (node.right != null) {
                	//通过哈希表,把子节点与父节点关联
                    map.put(node.right, node);
                    queueNode.offer(node.right);
                    queueSum.offer(rec);
                }
            }
        }

        return ret2;
    }

    public void getPath(TreeNode node) {
        List<Integer> temp = new LinkedList<Integer>();
        while (node != null) {
        	//添加叶节点
            temp.add(node.val);
            //从叶节点向上添加根节点
            node = map.get(node);
        }
        //反转数组
        Collections.reverse(temp);
        ret2.add(new LinkedList<Integer>(temp));
    }
}
